/*
 *      Filename: merge_ssort.c
 *       Version: 0.1.0
 *   Description: 链表归并排序
 *
 *        Author: wuyaowei
 *          Date: 2020-07-11
 *
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct ListNode {
     int val;
     struct ListNode *next;
} ListNode;


/*
 *  创建节点
 */
ListNode * createNode(int val) {
  ListNode *node = (ListNode *)malloc(sizeof(ListNode));
  node->val = val;
  node->next = NULL;
  return node;
}


//初始化链表
ListNode* init() {
	ListNode *ptr = NULL;
	ListNode *head = createNode(-1);
	 head->next = createNode(5);
	 head->next->next = createNode(4);
	 head->next->next->next =  createNode(3);
	 head->next->next->next->next =  createNode(0);
	 
	 return head;
}

//合并
ListNode* merge(ListNode *first, ListNode* second) {
	 
	    if(first == NULL) {
		return second;
            }
		
            if (second == NULL) {
		return first;
            }
           if(first->val < second->val) {
		first->next = merge(first->next, second);
		return first;
           } else {
		second->next = merge(second->next, first);
		return second;
           }
}


//先递归拆分，再合并
ListNode* splitList(ListNode *node) {
   ListNode* slow = node;
   ListNode* fast = node;
   ListNode* breakPoint = node;
    if(node == NULL || node->next == NULL) {
	return node;
    }
	
    while(fast != NULL && fast->next != NULL) {
	fast = fast->next->next;
	breakPoint = slow;
	slow = slow->next;
    }
    breakPoint->next = NULL;
    ListNode* first = splitList(node);
    ListNode* second = splitList(slow);
	
    return merge(first, second);
}

void main() {
  ListNode* ptr = NULL;

  ptr = splitList(init());
  while(ptr) {
      printf("%d ", ptr->val);
      ptr = ptr->next;
  }
  
  printf("\n");
}
